use std::{cmp::min, collections::HashMap, fs};

use serde_json::from_str;

use serde::{de::{self, MapAccess, Visitor}, Deserialize};


fn tarjan_search(edges: HashMap<u32, Vec<u32>>, num_nodes: u32) -> u32 {
    let mut dfn = vec![0; num_nodes as usize];
    let mut low = vec![0; num_nodes as usize];
    let mut dfn_cnt = 0;
    let mut stack = vec![];
    let mut in_stack = vec![false; num_nodes as usize];
    let mut top = 0;
    let mut scc = vec![0; num_nodes as usize];
    let mut scc_count = 0;

    fn tarjan(
        u: u32,
        dfn: &mut Vec<u32>,
        low: &mut Vec<u32>,
        dfn_cnt: &mut u32,
        stack: &mut Vec<u32>,
        in_stack: &mut Vec<bool>,
        top: &mut u32,
        scc: &mut Vec<u32>,
        scc_count: &mut u32,
        edges: &HashMap<u32, Vec<u32>>
    ) {
        *dfn_cnt += 1;
        dfn[u as usize] = *dfn_cnt;
        low[u as usize] = *dfn_cnt;
        stack.push(u);
        *top += 1;
        in_stack[u as usize] = true;
        for v in edges.get(&u).cloned().unwrap_or_default().iter() {
            if dfn[*v as usize] == 0 {
                tarjan(*v, dfn, low, dfn_cnt, stack, in_stack, top, scc, scc_count, edges);
                low[u as usize] = min(low[u as usize], low[*v as usize]);
            } else if in_stack[*v as usize] {
                low[u as usize] = min(low[u as usize], dfn[*v as usize]);
            }
        }

        if dfn[u as usize] == low[u as usize] {
            *scc_count += 1;
            while let Some(node) = stack.pop() {
                scc[node as usize] = *scc_count;
                in_stack[node as usize] = false;
                *top -= 1;
                if node == u {
                    break;
                }
            }
        }
    }

    for i in 0..num_nodes {
        if scc[i as usize] == 0 {
            tarjan(i, &mut dfn, &mut low, &mut dfn_cnt, &mut stack, &mut in_stack, &mut top, &mut scc, &mut scc_count, &edges);
        }
    }

    return scc_count

}

struct Testcase {
    content: Vec<OneCase>
}

// 将 key 为数字的 json 文件直接解析成 Vec
impl<'de> Deserialize<'de> for Testcase {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: de::Deserializer<'de>,
    {
        struct MyVisitor;

        impl<'d> Visitor<'d> for MyVisitor {
            type Value = Vec<OneCase>;

            fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
                f.write_str("an map of testcases")
            }

            fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
            where
                M: MapAccess<'d>,
            {
                let mut testcases = Vec::new();
                while let Some((key, value)) = access.next_entry::<&str, _>()? {
                    let pos = key.parse::<usize>().unwrap();
                    while testcases.len() < pos {
                        testcases.push(OneCase { content: HashMap::new() });
                    }
                    testcases[pos-1] = value;
                }
                Ok(testcases)
            }
        }
        Ok(Testcase{ content: deserializer.deserialize_map(MyVisitor)?})
    }
}

struct OneCase {
    content: HashMap<String, Vec<String>>
}

// 处理重复的键
impl<'de> Deserialize<'de> for OneCase {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: de::Deserializer<'de>,
    {
        struct MyVisitor;

        impl<'d> Visitor<'d> for MyVisitor {
            type Value = HashMap<String, Vec<String>>;

            fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
                f.write_str("an map of testcases")
            }

            fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
            where
                M: MapAccess<'d>,
            {
                let mut case: HashMap<String, Vec<String>> = HashMap::new();
                while let Some((key, value)) = access.next_entry::<&str, Vec<String>>()? {
                    case.entry(key.to_string()).and_modify(|v| v.extend(value.clone())).or_insert(value);
                }
                Ok(case)
            }
        }
        Ok(OneCase{ content: deserializer.deserialize_map(MyVisitor)?})
    }
}

pub fn count_provinces() -> String {
    let content = fs::read_to_string("district.json").expect("failed to parse json file");
    // 由于题目给定的数据格式相对一致，这里直接一次性 parse 出来。
    // 如果数据格式可能存在错误，这里可以换成更鲁棒的写法
    // parse 的过程中由于要维护各个测例的顺序，以及处理重复的键，这里手动实现了两个 Deserialize 方法
    let vec_json: Testcase = from_str(&content).expect("invalid data format");

    let mut answer = vec![];
    for testcase in vec_json.content.iter() {
        // 我们可以将输入数据所包含的所有市视为节点，如果某个市在另一个市对应的 value 中，则这两个市之间存在一条边
        // 那么，所属省份的个数，就是这个图的强连通分量的个数
        // 我们可以使用 tarjan 算法求强连通分量的个数
        // 先将市转换成用 u32 表示的节点，并记录边
        let mut id = 0;
        let mut key_to_id = HashMap::new();
        let mut edges: HashMap<u32, Vec<u32>> = HashMap::new();

        for (k, values) in testcase.content.iter() {
            let k_id = *key_to_id.entry(k.clone()).or_insert_with(|| {
                id += 1;
                id - 1
            });
            for v in values.iter() {
                if k != v {
                    let v_id = *key_to_id.entry(v.clone()).or_insert_with(|| {
                        id += 1;
                        id - 1
                    });
                    edges.entry(k_id).and_modify(|v| v.push(v_id)).or_insert(vec![v_id]);
                    edges.entry(v_id).and_modify(|v| v.push(k_id)).or_insert(vec![k_id]);
                }
            }
        }
        answer.push(tarjan_search(edges, id).to_string());
    }
    answer.join(",")
}
